package com.company.笔试.常用排序算法.堆排序;

import java.util.Arrays;

/**
 * @author ylr
 * @version 1.0.0
 * @ClassName HeapSortTest1.java
 * @Description TODO
 * @createTime 2022年03月02日 09:33:00
 */
public class HeapSortTest1 {
    public static void main(String []args){
        int []arr = {9,8,7,6,5,4,3,2,1,19,12,14,11,6,12};//length = 15
        sort(arr);
        System.out.println(Arrays.toString(arr));
    }

    public static void sort(int [] arr){
        //1构建初始化堆结构  从第一个非叶子节点开始arr.length/2 -1
        for (int i = (arr.length/2)-1; i >= 0 ; i--) {
            adjust(arr,i,arr.length);
        }
        // 未排序长度减一, 不断取出堆顶和堆尾交换,
        for (int i = arr.length-1; i >0 ; i--) {
            int tmp = arr[0];
            arr[0]=arr[i];
            arr[i]=tmp;//交换
            //调整
            adjust(arr,0,i);
        }


    }

    /**
     *
     * @param arr
     * @param i  当前下标
     * @param length 未排序长度
     */
    public static void adjust(int[] arr,int i,int length){
        //保存当前节点
        int tmp = arr[i];
        //当前节点的左右子节点先比较
        //左子节点2i+1 右2i+2
        for (int j = 2*i+1; j < length; j=2*j+1) {
            if (j+1<length&&arr[j]<arr[j+1]){
                //如果存在右子节点,且右子节点大则把指针指向右子节点
                j++;
            }
            // 得出较大的子节点再和当前节点比较,子节点大则交换,
            if (arr[j]>tmp){//子节点大则交换,
                arr[i]=arr[j];
                i=j;// 子节点成为当前节点进行下一次循环
            }else {//否则符合堆结构退出循环
                break;
            }
        }
        arr[i]=tmp;//tmp的最终位置是i
    }
}
